#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 239. 滑动窗口最大值.py
@time: 2022/1/19 19:49
@desc: https://leetcode-cn.com/problems/sliding-window-maximum/
> 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

@解题思路：
    1. python只有小顶堆
    2. 小顶堆的性质是第一个元素是最小的
    3. push可迭代变量的时候按第一个元素排序
    4. O(nlogn), O(n)
'''

import heapq
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(nums)
        heap = []
        res = []
        for i in range(k):
            heapq.heappush(heap, (-nums[i], i))
        res.append(-heap[0][0])
        for i in range(k, n):
            heapq.heappush(heap, (-nums[i], i))
            while heap[0][1] <= i-k:
                heapq.heappop(heap)
            res.append(-heap[0][0])

        return res


if __name__ == '__main__':
    nums = [9,10,9,-7,-4,-8,2,-6]
    k = 5
    res = Solution().maxSlidingWindow(nums, k)
    print(res)